//一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 
//
// 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 
//
// 问总共有多少条不同的路径？ 
//
// 
//
// 示例 1： 
//
// 
//输入：m = 3, n = 7
//输出：28 
//
// 示例 2： 
//
// 
//输入：m = 3, n = 2
//输出：3
//解释：
//从左上角开始，总共有 3 条路径可以到达右下角。
//1. 向右 -> 向下 -> 向下
//2. 向下 -> 向下 -> 向右
//3. 向下 -> 向右 -> 向下
// 
//
// 示例 3： 
//
// 
//输入：m = 7, n = 3
//输出：28
// 
//
// 示例 4： 
//
// 
//输入：m = 3, n = 3
//输出：6 
//
// 
//
// 提示： 
//
// 
// 1 <= m, n <= 100 
// 题目数据保证答案小于等于 2 * 10⁹ 
// 
// Related Topics 数学 动态规划 组合数学 👍 1443 👎 0


package leetcode.editor.cn;

import java.util.Arrays;

/**
 * 不同路径
 * @date 2022-06-22 09:37:05
 */
class P62_UniquePaths{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 //Solution solution = new P62_UniquePaths().new Solution();
		 Solution2 solution = new P62_UniquePaths().new Solution2();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/**
	 * 动态规划
	 * @param m 行
	 * @param n 列
	 * @return 空间复杂度为O(m*n)
	 */
    public int uniquePaths(int m, int n) {
		int[][] dp = new int[m][n];
		for (int i = 0; i < m; i++) {
			dp[i][0] = 1;//初始化第0列为1，
		}
		for (int i = 0; i < n; i++) {
			dp[0][i] = 1;//初始化第0行为1，0行0列均处于边界故均为1
		}
		/**
		 * dp[i][j] 是到达 i, j 最多路径
		 * 到达某块的最多路径等于到达左边的最多路径+到达其上面的最多路径
		 */
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				dp[i][j] = dp[i-1][j] + dp[i][j-1];
			}
		}
		return dp[m-1][n-1];
    }
}
//leetcode submit region end(Prohibit modification and deletion)
class Solution1{
	/**
	 * 优化一
	 * @param m
	 * @param n
	 * @return
	 */
	public int uniquePaths(int m, int n) {
		int[] cur = new int[n];//用于存放到达当前行的最多路径
		int[] pre = new int[n];//用于存放到达当前行上一行的最多路径
		Arrays.fill(cur,1);//初始化为1
		Arrays.fill(pre,1);
		for (int i = 0; i < m; i++) {//遍历行
			for (int j = 0; j < n; j++) {
				cur[j] = cur[j-1] + pre[j];
			}
			pre = cur.clone();//用于数组的复制
		}
		return cur[n-1];
	}
}
	class Solution2{
		/**
		 * 优化二
		 * @param m
		 * @param n
		 * 令m为行、n为列 优化1：
		 * 行列两层循环中的循环体cur[j] = pre[j] + cur[j-1] ，cur[j] 表示遍历到的从起点到第i行第j列的路径数，
		 * 它等于当前第i行第j-1列即 cur[j-1]的值 加上 上一行第j列的值pre[j] 内层循环一次后即计算完了第i行各列的值，在计算下一行第i+1行之前执行pre = cur.clone();
		 * 即第i行的值就是第i+1行的前一行，两层循环完以后最后要到达的终点的行的值存于pre数组中，所以取出 pre[n-1]即可
		 * 优化2：相比优化1，少了pre数组，cur[j] += cur[j-1] 即 cur[j] = cur[j-1] + cur[j]
		 * 未赋值之前右边的cur[j] 始终表示当前行第i行的上一行第j列的值，赋值之后左边的cur[j]表示当前行第i行第j列的值，
		 * cur[j-1] 表示当前行第i行第j-1列的值(cur[j-1] 在计算cur[j]之前就已经计算了，所以表示的是当前行而不是上一行 )， 思路跟优化1是一样的，除了少用了一个数组
		 */
		public int uniquePaths(int m, int n) {
			int[] cur = new int[n];
			Arrays.fill(cur,1);
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					cur[j] = cur[j-1] + cur[j];
				}
			}
			return cur[n-1];
		}
	}

}
